package graph2.component;

import graph2.Graph;

/**
 * 查看一个图的联通分量 采用深度优先遍历的方式 一个递归完成就是一个联通分量
 * 用一个visited数组标识一个节点是否被遍历过
 */
public class Component {
    /**
     * 图的引用
     */
    private Graph graph;
    /**
     * 节点是否被遍历过
     */
    private boolean[] visited;
    /**
     * 联通分量的数量
     */
    private int ccount;
    /**
     * 表示哪个节点在哪个联通分量
     */
    private int[] id;


    public Component(Graph graph) {
        this.graph = graph;
        id = new int[graph.V()];
        ccount = 0;
        visited = new boolean[graph.V()];

        for (int i = 0; i < graph.V(); i++) {
            if(!visited[i]){
                dfs(i);
                ccount++;
            }
        }
    }

    /**
     * 深度优先遍历
     *
     * @param i
     */
    private void dfs(int i) {
        visited[i] = true;
        id[i] = ccount;
        Iterable<Integer> nodes = graph.adj(i);
        for (Integer node : nodes) {
            if (!visited[node]) {
                dfs(node);
            }
        }
    }


    /**
     * 返回联通分量的数量
     *
     * @return
     */
    public int count() {
        return ccount;
    }

    /**
     * 返回一个点所在的联通分量
     *
     * @param v
     * @return
     */
    public int getByPoint(int v) {
        return id[v];
    }

    /**
     * 两个节点是否在一个联通分量
     *
     * @param v
     * @param w
     * @return
     */
    public boolean isConnected(int v, int w) {
        return id[v] == id[w];
    }


}
